package 树.二叉查找树;

import 树.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Created by yang on 2016/9/1.
 */
public class SortTree {

    /**
     * The function define the insert operation of 'Binary Sort Tree'
     *
     * 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
     * 若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
     * 左、右子树也分别为二叉排序树；
     * 没有键值相等的结点。
     * {@code insert = binaryTree.insertOfBinarySortTree(insert , 3)}
     * {@code insert = binaryTree.insertOfBinarySortTree(insert , 10)}
     * @param val : value ready to insert
     * @return
     */
    public TreeNode insertOfBinarySortTree(TreeNode sortTree , int val) {

        TreeNode current = sortTree;

        // 1. compare from root node
        // if less than val of root node
        // the node ready to insert is one of the lChilds of root
        if (val < current.val) {
            // 2. lChild is null , then insert node
            if (current.lChild == null) {
                TreeNode tmp = new TreeNode(val);
                current.lChild = tmp;
            } else {
                // 3. otherwise , repeat step 1 with lChild
                insertOfBinarySortTree(current.lChild , val);
            }
        } else if (val > current.val) {
            if (current.rChild == null) {
                TreeNode tmp = new TreeNode(val);
                current.rChild = tmp;
            } else {
                insertOfBinarySortTree(current.rChild , val);
            }
        }

        return current;
    }

    public TreeNode deleteOfSortTree(TreeNode treeNode, int index) {

        TreeNode current = treeNode;
        int indexOfDelele = 0;
        // 找到index节点
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        if (current != null) {
            queue.offer(current);
        }
        while (!queue.isEmpty()) {
            TreeNode tmp = queue.poll();
            if (index == indexOfDelele) {
                // 删除节点
                // 判断删除的节点有无孩子节点
                // 左右孩子都为空
                if (tmp.lChild == null & tmp.rChild == null) {
                    tmp = null;
                    break;
                    // 只有左孩子
                }else if (tmp.lChild != null & tmp.rChild == null) {
                    tmp = tmp.lChild;
                    break;
                    // 只有右孩子
                }else if (tmp.rChild != null & tmp.lChild == null) {
                    tmp = tmp.rChild;
                    break;
                    // 左右孩子都不为空
                }else if (tmp.rChild != null & tmp.lChild != null) {
                    // 删除的节点左右孩子都有
                    // 从左子树寻找替换节点
                    findAndReplaceL(tmp);
                    // 2. 或者在右边找到最小的节点代替被删除的节点，这个节点必然没有左孩子
                }
            }
            indexOfDelele++;
            if (current.lChild != null) {
                queue.offer(current.lChild);
            }
            if (current.rChild != null) {
                queue.offer(current.rChild);
            }
        }

        return treeNode;
    }

    /**
     *
     * @param data
     */
    public void findAndReplaceL(TreeNode data) {
// 1. 则在左边找到最大的节点代替被删除的节点，这个节点必然没有右孩子
        TreeNode replace = findMax(data.lChild);
        // 1.1 判断有无左子树
        if (replace.lChild != null) {
            // 保存replace的左孩子
            TreeNode lChild = replace.lChild;
            // 置空replace的左孩子
            replace.lChild = null;
            // 保存没有左右孩子的replace节点
            TreeNode tmpOfreplace = replace;
            // 将repalce节点使用其左孩子替换
            replace = lChild;
            // 将需要删除节点的左右孩子还原到新的节点
            tmpOfreplace.lChild = data.lChild;
            tmpOfreplace.rChild = data.rChild;
            // 插入新节点
            data = tmpOfreplace;
        }else {
            TreeNode tmpOfreplace = replace;
            replace = null;
            tmpOfreplace.lChild = data.lChild;
            tmpOfreplace.rChild = data.rChild;
            data = tmpOfreplace;
        }
    }

    /**
     *
     * @param data node of been removed
     */
    public void findAndReplaceR(TreeNode data) {

        TreeNode replace = findMin(data.rChild);
        if (replace.rChild != null) {
            // 保存右节点
            TreeNode rChild = replace.rChild;
            // 置空右节点
            replace.rChild = null;
            // 保存没有左右节点的replace节点
            TreeNode tmpOfReplace = replace;
            tmpOfReplace.rChild = data.rChild;
            tmpOfReplace.lChild = data.lChild;
            replace = rChild;
            data = tmpOfReplace;

        }else {

            TreeNode tmpOfReplace = replace;
            replace = null;
            tmpOfReplace.lChild = data.lChild;
            tmpOfReplace.rChild = data.rChild;
            data = tmpOfReplace;
        }
    }

    /**
     * find the maximum node of the binary sort tree
     * @param treeNode
     * @return
     */
    public TreeNode findMax(TreeNode treeNode) {

        if (treeNode == null || treeNode.rChild == null) {
            return treeNode;
        }
        return findMax(treeNode.rChild);
    }

    /**
     * find the minimum node of the binary sort tree
     * @param treeNode
     * @return
     */
    public TreeNode findMin(TreeNode treeNode) {

        if (treeNode == null || treeNode.lChild == null) {
            return treeNode;
        }

        return findMin(treeNode.lChild);
    }
}
